﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingAlgorithms.Exchange
{
    /// <summary>
    /// 冒泡排序-交换排序
    /// </summary>
    /// <remarks>
    /// 分类 -------------- 内部比较排序
    /// 数据结构 ---------- 数组
    /// 最差时间复杂度 ---- O(n^2)
    /// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
    /// 平均时间复杂度 ---- O(n^2)
    /// 所需辅助空间 ------ O(1)
    /// 稳定性 ------------ 稳定
    /// </remarks>
    public class BubbleSort
    {
        //定义一个静态变量来保存类的实例
        private static BubbleSort _uniqueInstance = null;

        //定义一个标识确保线程同步
        private static readonly object locker = new object();

        /// <summary>
        /// 私有化构造函数，使外界不能创建该类实例
        /// </summary>
        private BubbleSort()
        {
        }

        public static BubbleSort Instance
        {
            get
            {
                if (_uniqueInstance == null)
                {
                    lock (locker)
                    {
                        if (_uniqueInstance == null)
                        {
                            _uniqueInstance = new BubbleSort();

                        }
                    }
                }
                return _uniqueInstance;
            }
        }


        /// <summary>
        /// 倒序排序
        /// </summary>
        /// <param name="a">被排序数组</param>
        /// <param name="n">数组长度</param>
        public void SortDesc(int[] a, int n)
        {
           
        }

        /// <summary>
        /// 顺序排序
        /// </summary>
        /// <param name="a">被排序数组</param>
        /// <param name="n">数组长度</param>
        public void SortAsc(int[] a, int n)
        {
            for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
            {
                for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
                {
                    if (a[i] > a[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
                    {
                        Swap(a, i, i + 1);
                    }
                }
            }
        }

        void Swap(int[] a, int i, int j)
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}
